#define DEBUG
#include <cstdio>
#define MAXN 1000000
#define MAXM MAXN

using namespace std;

class Graph {
public:
  int n, m, ind[MAXN+1], to[MAXM+1], link[MAXM+1];

  void init(int n) {
    this->n = n, m=0;
    for (int i=1; i<=n; i++) {
      ind[i] = 0;
    }
  }

  void addSide(int u, int v) {
    m++;
    to[m] = v;
    link[m] = ind[u];
    ind[u] = m;
  }
};

void dp(int o, Graph *g, const int *b, int *book, int ver, int f[][2][3], int root, int pos=0) {
  book[o] = ver;
  f[o][0][0] = f[o][1][0] = 0;
  for (int i=g->ind[o]; i; i=g->link[i]) {
    int x=g->to[i];
    dp(g->to[i], g, b, book, ver, f, pos);
    if ((o!=root || !pos) && (f[o][1][0]<f[x][0][0] || (f[o][1][0]==f[x][0][0] && f[o][1][1]<f[x][0][1]))) {
      f[o][1][0] = f[x][0][0];
      f[o][1][1] = f[x][1][0];
      f[o][1][2] = x;
    }
  }
  if (o==root && pos) {
    f[o][1][0] = f[pos][0][0];
    f[o][1][1] = f[pos][1][0];
    f[o][1][2] = pos;
  }
  for (int i=g->ind[o]; i; i=g->link[i]) {
    int x=g->to[i];
    if (f[x][0][0]>f[x][1][0] || (f[x][0][0]==f[x][1][0] && f[x][0][1]>f[x][1][1])) {
      f[o][0][0] += f[x][0][0];
      f[o][0][1] += f[x][0][1];
      if (x!=f[o][1][2]) {
	f[o][1][0] += f[x][0][0];
	f[o][1][1] += f[x][0][1];
      }
    } else {
      f[o][0][0] += f[x][1][0];
      f[o][0][1] += f[x][1][1];
    }
  }
  if (o==pos) {
    f[o][1][0] = f[o][1][1] = f[o][1][2] = 0;
  }
}

void fillAns(int ans[][2], int o, const int f[][2][3], int x, const int b[], const Graph *g) {
  if (f[o][x][2]) {
    ans[++ans[0][0]][0] = o;
    ans[ans[0][0]][1] = f[o][x][2];
    ans[0][1] += b[o]!=b[f[o][x][2]];
  }
  for (int i=g->ind[o]; i; i=g->link[o]) {
    if (g->to[i]!=f[o][x][2]) {
      int x=g->to[i];
      if (f[x][0][0]>f[x][1][0] || (f[x][0][0]==f[x][1][0] && f[x][0][1]>f[x][1][1])) {
	fillAns(ans, g->to[i], f, 0, b, g);
      } else {
	fillAns(ans, g->to[i], f, 1, b, g);
      }
    } else {
      fillAns(ans, g->to[i], f, 0, b, g);
    }
  }
}

void solve(int o, Graph *g, const int *a, const int *b, int *book, int ver, int ans[][2]) {
  for (; book[o]!=ver; o=a[o]) {
    book[o] = ver;
  }
  int temp = g->to[g->ind[o]];
  g->ind[o] = g->link[g->ind[o]];

  static int f[2][MAXN+1][2][3];
  dp(o, g, b, book, ver, f[0], o);
  dp(o, g, b, book, ver, f[1], o, temp);

  if (f[0][o][0][0]>f[0][o][1][0] || (f[0][o][0][0]==f[0][o][1][0] && f[0][o][0][1]>=f[0][o][1][1])) {
    if (f[0][o][0][0]>f[1][o][1][0] || (f[0][o][0][0]==f[1][o][1][0] && f[0][o][0][1]>=f[1][o][1][1])) {
      fillAns(ans, o, f[0], 0, b, g);
    } else {
      fillAns(ans, o, f[1], 1, b, g);
    }
  } else {
    if (f[0][o][1][0]>f[1][o][1][0] || (f[0][o][1][0]==f[1][o][1][0] && f[0][o][1][1]>=f[1][o][1][1])) {
      fillAns(ans, o, f[0], 1, b, g);
    } else {
      fillAns(ans, o, f[0], 1, b, g);
    }
  }
}

int main() {
#ifdef DEBUG
  freopen("4760.in", "r", stdin);
  freopen("4760.out", "w", stdout);
#endif

  int t;
  scanf("%d", &t);
  for (int ti=1; ti<=t; ti++) {
    static int a[MAXN+1], b[MAXN+1], book[MAXN+1];
    static Graph g;
    int n;
    scanf("%d", &n);
    g.init(n);
    for (int i=1; i<=n; i++) {
      scanf("%d %d", a+i, b+i);
      g.addSide(a[i], i);
    }

    static int ans[MAXN+1][2];
    ans[0][0]=ans[0][1]=0;
    for (int i=1; i<=n; i++) {
      if (book[i]!=ti) {
	solve(i, &g, a, b, book, ti, ans);
      }
    }
    for (int i=0; i<=ans[0][0]; i++) {
      printf("%d %d\n", ans[i][0], ans[i][1]);
    }
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}
